A lower bound is an estimate, heuristic or calculated value that yoo know lies at or below the smallest possible value of an unknown value or function. For example, if you are looking for the road distance between two locations, you know this will be at least as large as the Euclidean dstace between them (crow flies distance). Knowing a lower bound can sometimes allow whole branches of a search tree or similar structure to be pruned. For example, if you are looking for the smallest value in a tree and have found a node with value 7, and then consider an alternative branch in the tree where a heuristic tells you that the lower bound for nodes in the branch is 12, you can safely ignore the entre sub-tree.
Used on Chap. 4: pages 74, 81